{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Pairs of Interchangeable Rectangles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #math #counting #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #数学 #计数 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: interchangeableRectangles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可互换矩形的组数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>用一个下标从 <strong>0</strong> 开始的二维整数数组&nbsp;<code>rectangles</code> 来表示 <code>n</code> 个矩形，其中 <code>rectangles[i] = [width<sub>i</sub>, height<sub>i</sub>]</code> 表示第 <code>i</code> 个矩形的宽度和高度。</p>\n",
    "\n",
    "<p>如果两个矩形 <code>i</code> 和 <code>j</code>（<code>i &lt; j</code>）的宽高比相同，则认为这两个矩形 <strong>可互换</strong> 。更规范的说法是，两个矩形满足&nbsp;<code>width<sub>i</sub>/height<sub>i</sub> == width<sub>j</sub>/height<sub>j</sub></code>（使用实数除法而非整数除法），则认为这两个矩形 <strong>可互换</strong> 。</p>\n",
    "\n",
    "<p>计算并返回&nbsp;<code>rectangles</code> 中有多少对 <strong>可互换 </strong>矩形。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rectangles = [[4,8],[3,6],[10,20],[15,30]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>下面按下标（从 0 开始）列出可互换矩形的配对情况：\n",
    "- 矩形 0 和矩形 1 ：4/8 == 3/6\n",
    "- 矩形 0 和矩形 2 ：4/8 == 10/20\n",
    "- 矩形 0 和矩形 3 ：4/8 == 15/30\n",
    "- 矩形 1 和矩形 2 ：3/6 == 10/20\n",
    "- 矩形 1 和矩形 3 ：3/6 == 15/30\n",
    "- 矩形 2 和矩形 3 ：10/20 == 15/30\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rectangles = [[4,5],[7,8]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不存在成对的可互换矩形。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == rectangles.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>rectangles[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= width<sub>i</sub>, height<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-pairs-of-interchangeable-rectangles](https://leetcode.cn/problems/number-of-pairs-of-interchangeable-rectangles/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-pairs-of-interchangeable-rectangles](https://leetcode.cn/problems/number-of-pairs-of-interchangeable-rectangles/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[4,8],[3,6],[10,20],[15,30]]', '[[4,5],[7,8]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        n = len(rectangles)\n",
    "        res = 0\n",
    "        '''\n",
    "        for i in range(n):\n",
    "            temp = rectangles[i][0]/rectangles[i][1]\n",
    "            for j in range(i+1,n):\n",
    "                if rectangles[j][0]/rectangles[j][1] == temp:\n",
    "                    res+=1\n",
    "        '''\n",
    "        temp_dict = {}\n",
    "        for i in range(n):\n",
    "            temp = rectangles[i][0]/rectangles[i][1]\n",
    "            if temp not in temp_dict:\n",
    "                temp_dict[temp]=1\n",
    "            else:\n",
    "                temp_dict[temp]+=1\n",
    "        \n",
    "        for k in temp_dict:\n",
    "            if temp_dict[k]>=2:\n",
    "                res+=sum([i for i in range(temp_dict[k])])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        dic = {}\n",
    "        for i in rectangles:\n",
    "            tmp = i[0]/i[1]\n",
    "            if tmp in dic:\n",
    "                res += dic[tmp]\n",
    "                dic[tmp] += 1\n",
    "            else:\n",
    "                dic[tmp] = 1\n",
    "        print(dic)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        m = defaultdict(int)\n",
    "        ans = 0\n",
    "        for w, h in rectangles:\n",
    "            v = w / h\n",
    "            ans += m[v]\n",
    "            m[v] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        res = 0\n",
    "        for tmp in rectangles:\n",
    "            ratio = tmp[0]/tmp[1]\n",
    "            if ratio not in dic:\n",
    "                dic[ratio] = 1\n",
    "            else:\n",
    "                dic[ratio] += 1\n",
    "        \n",
    "        for val in dic.values():\n",
    "            res += val*(val-1)//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for width, height in rectangles:\n",
    "            d[width / height] += 1\n",
    "        count_mappings = defaultdict(int)\n",
    "        for v in d.values():\n",
    "            if v > 1:\n",
    "                count_mappings[v] += 1\n",
    "        res = 0\n",
    "        for k, v in count_mappings.items():\n",
    "            res += v * k * (k - 1) // 2\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        cnt = Counter()\n",
    "        for x, y in rectangles:\n",
    "            cnt[x/y] += 1\n",
    "        ans = 0\n",
    "        for k, v in cnt.items():\n",
    "            ans += (v) * (v - 1) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        dic={}\n",
    "        res=0\n",
    "        for width,height in rectangles:\n",
    "            if width/height in dic:\n",
    "                res+=dic[width/height]\n",
    "                dic[width/height]+=1\n",
    "            else:\n",
    "                dic[width/height]=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        dic={}\n",
    "        res=0\n",
    "        for width,height in rectangles:\n",
    "            if width/height in dic:\n",
    "                res+=dic[width/height]\n",
    "                dic[width/height]+=1\n",
    "            else:\n",
    "                dic[width/height]=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        ans = 0\n",
    "        for x, y in rectangles:\n",
    "            ans += d[x/y]\n",
    "            d[x/y] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        d = Counter()\n",
    "        for w, h in rectangles:\n",
    "            x = w / h\n",
    "            ans += d[x]\n",
    "            d[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        mul = 10 ** 12\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x, y in rectangles:\n",
    "            tmp = x * mul / y \n",
    "            ans += cnt[tmp]\n",
    "            cnt[tmp] += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        d = {}\n",
    "        for x, y in rectangles:\n",
    "            gcd = math.gcd(x, y)\n",
    "            d[(x // gcd, y// gcd)] = d.get((x // gcd, y// gcd), 0) + 1\n",
    "        ans = 0\n",
    "        for v in d.values():\n",
    "            ans += (v * (v - 1)) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        c = Counter()\n",
    "        ans = 0\n",
    "        for x, y in rectangles:\n",
    "            g = x/y\n",
    "            ans += c[g]\n",
    "            c[g] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        answer = 0\n",
    "        d = defaultdict(int)\n",
    "        for i in rectangles:\n",
    "            d[i[0]/i[1]] += 1\n",
    "        for i in d:\n",
    "            n = d[i]\n",
    "            answer += n*(n-1)/2\n",
    "        return int(answer)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for a, b in rectangles:\n",
    "            d[float(a)/b] += 1\n",
    "        ans = 0\n",
    "        for i in d.values():\n",
    "            if i >= 2:\n",
    "                ans += i * (i-1) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        from math import gcd\n",
    "        n = len(rectangles)\n",
    "        d = {}\n",
    "        cnt = 0\n",
    "        for w, h in rectangles:\n",
    "            _gcd = gcd(w, h)\n",
    "            key = (w // _gcd, h // _gcd)\n",
    "            if key in d:\n",
    "                cnt += d[key]\n",
    "                d[key] += 1\n",
    "            else:\n",
    "                d[key] = 1\n",
    "        return cnt\n",
    "        # return sum(1 for i in range(n) for j in range(i + 1, n) \n",
    "        #     if rectangles[i][0] * rectangles[j][1] == rectangles[i][1] * rectangles[j][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        mp = defaultdict(int)\n",
    "        for w, h in rectangles:\n",
    "            ans += mp[w / h]\n",
    "            mp[w / h] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        ans = 0\n",
    "        for x, y in rectangles:\n",
    "            ans += d[x/y]\n",
    "            d[x/y] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, a: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        c = Counter()\n",
    "        for i, x in enumerate(a):\n",
    "            t = x[0] / x[1]\n",
    "            res += c[t]\n",
    "            c[t] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        cnt = Counter()\n",
    "        ret = 0\n",
    "        for a, b in rectangles:\n",
    "            c = a / b\n",
    "            ret += cnt[c]\n",
    "            cnt[c] += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        ans = 0\n",
    "        for x, y in rectangles:\n",
    "            g = x/y\n",
    "            ans += d[g]\n",
    "            d[g] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        c = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for w,h in rectangles:\n",
    "            x = w/h\n",
    "            c[x] += 1\n",
    "        for k,v in c.items():\n",
    "            ans += (v-1)*v//2\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        d = {}\n",
    "        for i in rectangles:\n",
    "            t = i[0] / i[1]\n",
    "            d[t] = d.get(t,0) + 1\n",
    "        ret = 0\n",
    "        for key, value in d.items():\n",
    "            ret += value*(value-1) // 2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def interchangeableRectangles(self, rectangles):\n",
    "        \"\"\"\n",
    "        :type rectangles: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dic = {}\n",
    "        ans = 0\n",
    "        for x in rectangles:\n",
    "            gcd = math.gcd(x[0], x[1])\n",
    "            x[0] /= gcd\n",
    "            x[1] /= gcd\n",
    "            tmp = int(x[0] * 9982443553 + x[1])\n",
    "            dic.setdefault(tmp, 0)\n",
    "            ans += dic[tmp]\n",
    "            dic[tmp] += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        c = Counter()\n",
    "        ans = 0\n",
    "        for x, y in rectangles:\n",
    "            g = x/y\n",
    "            ans += c[g]\n",
    "            c[g] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gcd1(p: int, q: int) -> int:\n",
    "    r = p % q\n",
    "    while r != 0:\n",
    "        p = q\n",
    "        q = r\n",
    "        r = p % q\n",
    "    return q\n",
    "\n",
    "def gcd2(p: int, q: int) -> int:\n",
    "    if q == 0:\n",
    "        return p\n",
    "    return gcd2(q, p % q)\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        counter = defaultdict(int)\n",
    "        res = 0\n",
    "        for w, h in rectangles:\n",
    "            x = gcd1(w, h)\n",
    "            w, h = w // x, h // x\n",
    "            res += counter[(w, h)]\n",
    "            counter[(w, h)] += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        c = Counter()\n",
    "        ans = 0\n",
    "        for x, y in rectangles:\n",
    "            g = x/y\n",
    "            ans += c[g]\n",
    "            c[g] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution(object):\n",
    "    def interchangeableRectangles(self, rectangles):\n",
    "        n=len(rectangles)\n",
    "        ans=0\n",
    "        def cal(n):\n",
    "            return n*(n-1)//2\n",
    "        m=defaultdict(int)\n",
    "        for r in rectangles:\n",
    "            w,h=r[0],r[1]\n",
    "            m[w/h]+=1\n",
    "        for val in m.values():\n",
    "            ans+=cal(val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        # ratios = [0] * len(rectangles)\n",
    "        s = {}\n",
    "        for i, r in enumerate(rectangles):\n",
    "\n",
    "            ratio = r[0] / r[1]\n",
    "            if ratio not in s:\n",
    "                s[ratio] = 0\n",
    "            s[ratio] += 1\n",
    "\n",
    "        ans = 0\n",
    "        for v in s.values():\n",
    "            if v > 1:\n",
    "                ans += v * (v-1) // 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        ratios = [0] * len(rectangles)\n",
    "        for i, r in enumerate(rectangles):\n",
    "            ratios[i] = r[0] / r[1]\n",
    "        \n",
    "        \n",
    "        s = {}\n",
    "        for r in ratios:\n",
    "            if r not in s:\n",
    "                s[r] = 0\n",
    "            s[r] += 1\n",
    "        # print(s)\n",
    "\n",
    "        ans = 0\n",
    "        for v in s.values():\n",
    "            if v > 1:\n",
    "                ans += v * (v-1) // 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for w, h in rectangles:\n",
    "            g = self.gcd(w, h)\n",
    "            cnt[(w // g, h // g)] += 1\n",
    "        ans = 0\n",
    "        for m in cnt.values():\n",
    "            ans += m * (m-1) // 2\n",
    "        return ans\n",
    "    def gcd(self, x, y):\n",
    "        while x != 0:\n",
    "            x, y = y%x, x\n",
    "        return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        res=0\n",
    "        cnt=Counter()\n",
    "        for x,y in rectangles:\n",
    "            g=gcd(x,y)\n",
    "            x//=g\n",
    "            y//=g\n",
    "            res+=cnt[(x,y)]\n",
    "            cnt[(x,y)]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        c = Counter()\n",
    "        ans = 0\n",
    "        for x, y in rectangles:\n",
    "            ans += c[x/y]\n",
    "            c[x/y] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        ratio_dict = defaultdict(int)\n",
    "        res = 0\n",
    "\n",
    "        for [w, h] in rectangles:\n",
    "            gcd = math.gcd(w, h)\n",
    "            r = (w // gcd, h // gcd)\n",
    "            \n",
    "            ratio_dict[r] += 1\n",
    "            res += ratio_dict[r] - 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        count = {}  # { W / H : Count }\n",
    "        res = 0\n",
    "\n",
    "        for w, h in rectangles:\n",
    "            # Increment the count for the ratio\n",
    "            count[w / h] = 1 + count.get(w / h, 0)\n",
    "\n",
    "        for c in count.values():\n",
    "            res += (c * (c - 1)) // 2\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        n = len(rectangles)\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for w, h in rectangles:\n",
    "            x = gcd(w, h)\n",
    "            a, b = w // x, h // x\n",
    "            ans += cnt[a, b]\n",
    "            cnt[a, b] += 1\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        d=defaultdict(int)\n",
    "        ans=0\n",
    "        for i,j in rectangles:\n",
    "            temp=i/j\n",
    "            ans+=d[temp]\n",
    "            d[temp]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        c = Counter()\n",
    "        ans = 0\n",
    "        for x, y in rectangles:\n",
    "            g = gcd(x, y)\n",
    "            x //= g\n",
    "            y //= g\n",
    "            ans += c[(x, y)]\n",
    "            c[(x, y)] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        c = Counter()\n",
    "        ans = 0\n",
    "        for x, y in rectangles:\n",
    "            g = gcd(x, y)\n",
    "            x //= g\n",
    "            y //= g\n",
    "            ans += c[(x, y)]\n",
    "            c[(x, y)] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        ret = 0\n",
    "        hashMap = collections.defaultdict(int)\n",
    "        for r in rectangles:\n",
    "            c = self.gcd(r[0], r[1])\n",
    "            r[0] //= c\n",
    "            r[1] //= c\n",
    "            r = tuple(r)\n",
    "            hashMap[r] += 1\n",
    "        for _, val in hashMap.items():\n",
    "            if val > 1:\n",
    "                ret += val * (val - 1) // 2\n",
    "\n",
    "        return ret\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "    def gcd(self, a, b):\n",
    "        if a < b: return self.gcd(b, a)\n",
    "        if a % b == 0: return b\n",
    "        return self.gcd(b, a % b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        # 计算最简分数 \n",
    "        d = Counter()\n",
    "        for i,j in rectangles:\n",
    "            p, q = self.pair(i,j)\n",
    "            d[(p,q)] += 1 \n",
    "        rv = 0 \n",
    "        for k in d:\n",
    "            v = d[k] \n",
    "            rv += v*(v-1)//2 \n",
    "        return rv \n",
    "\n",
    "    def gcd(self, p, q):\n",
    "        k, v = divmod(p, q)\n",
    "        if v==0:\n",
    "            return q\n",
    "        return self.gcd(q, v) \n",
    "\n",
    "    def pair(self, p, q):\n",
    "        t = self.gcd(p,q) \n",
    "        return p//t, q//t \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        ret = 0\n",
    "        hashMap = collections.defaultdict(int)\n",
    "        for height, width in rectangles:\n",
    "            factor = gcd(width, height)\n",
    "            height //= factor\n",
    "            width //= factor\n",
    "            hashMap[(height, width)] += 1\n",
    "        for _, val in hashMap.items():\n",
    "            ret += (val - 1) * val // 2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from math import gcd\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        ratio_counter = defaultdict(int)\n",
    "\n",
    "        # 使用最大公约数来表示比率，从而避免浮点数的不精确性\n",
    "        for width, height in rectangles:\n",
    "            greatest_common_divisor = gcd(width, height)\n",
    "            ratio = (width // greatest_common_divisor, height // greatest_common_divisor)\n",
    "            ratio_counter[ratio] += 1\n",
    "\n",
    "        # 对于每种宽高比的矩形数量 n，有 n*(n-1)/2 对可互换的矩形\n",
    "        result = 0\n",
    "        for count in ratio_counter.values():\n",
    "            result += count * (count - 1) // 2\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def myGCD(m: int, n: int) -> int:\n",
    "    r = m % n\n",
    "    while r != 0:\n",
    "        m = n\n",
    "        n = r \n",
    "        r = m % n\n",
    "    return n\n",
    "\n",
    "def myGCD1(p: int, q: int) -> int:\n",
    "    if q == 0:\n",
    "        return p\n",
    "    return myGCD1(q, p % q)\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        counter = defaultdict(int)\n",
    "        res = 0\n",
    "        for w, h in rectangles:\n",
    "            x = myGCD1(w, h)\n",
    "            w, h = w // x, h // x\n",
    "            res += counter[(w, h)]\n",
    "            counter[(w, h)] += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        ratio_dict = {}\n",
    "        for [w, h] in rectangles:\n",
    "            gcd = self.gcd(w, h)\n",
    "            ratio = (w // gcd, h // gcd)\n",
    "            if ratio in ratio_dict:\n",
    "                ratio_dict[ratio] += 1\n",
    "            else:\n",
    "                ratio_dict[ratio] = 1\n",
    "\n",
    "        totle_time = 0\n",
    "        \n",
    "        for _, occur_time in ratio_dict.items():\n",
    "            totle_time += (occur_time) * (occur_time - 1) // 2\n",
    "\n",
    "        return totle_time\n",
    "\n",
    "    def gcd(self, a, b):\n",
    "        if b > a:\n",
    "            a, b = b, a\n",
    "        if a % b == 0:\n",
    "            return b\n",
    "        else:\n",
    "            return self.gcd(b, a % b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        return sum([i*(i-1)//2 for i in collections.Counter([j[0]/j[1] for j in rectangles]).values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        return sum(x*(x-1)//2 for x in Counter([b/a for a,b in rectangles]).values())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        return sum([x*(x-1)//2 for x in (Counter([w/h for w,h in rectangles]).values())])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        n = len(rectangles)\n",
    "        \n",
    "        # 计算每个矩形的长宽比例\n",
    "        ratios = [rect[0] / rect[1] for rect in rectangles]\n",
    "        \n",
    "        # 统计每个比例出现的频次\n",
    "        frequnce = Counter(ratios)\n",
    "        \n",
    "        # 统计相同比例的矩形对的数量\n",
    "        count = 0\n",
    "        for f in frequnce.values():\n",
    "            if f > 1:\n",
    "                count += math.comb(f, 2)\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        return sum([i*(i-1)//2 for i in collections.Counter([j[0]/j[1] for j in rectangles]).values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:\n",
    "        rate = []\n",
    "        count = 0\n",
    "        for i in rectangles:\n",
    "            rate.append(i[0]/i[1])\n",
    "        for k,v in Counter(rate).items():\n",
    "            if k:\n",
    "                count += comb(v,2)\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
